package com.skh.stack;

import java.util.Stack;

/**
 * @Author: skh
 * @Date: 2019/7/4 16:01
 * @Description: 比较含退格的字符串
 */
public class BackspaceCompare {

    /*
    给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

    示例 1：

    输入：S = "ab#c", T = "ad#c"
    输出：true
    解释：S 和 T 都会变成 “ac”。
    示例 2：

    输入：S = "ab##", T = "c#d#"
    输出：true
    解释：S 和 T 都会变成 “”。
    示例 3：

    输入：S = "a##c", T = "#a#c"
    输出：true
    解释：S 和 T 都会变成 “c”。
    示例 4：

    输入：S = "a#c", T = "b"
    输出：false
    解释：S 会变成 “c”，但 T 仍然是 “b”。
     
    提示：
    1 <= S.length <= 200
    1 <= T.length <= 200
    S 和 T 只含有小写字母以及字符 '#'。
     */

    public boolean backspaceCompare(String S, String T) {
        if (getResult(S).equals(getResult(T))) {
            return true;
        }
        return false;
    }

    public String getResult(String s) {
        Stack<Character> stackS = new Stack();
        char[] temp = s.toCharArray();
        for (char c : temp) {
            if (c == '#') {
                if (!stackS.isEmpty()) {
                    stackS.pop();
                }
            }else {
                stackS.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Character stack : stackS) {
            sb.append(stack);
        }
        return sb.toString();
    }
}
